package algorithm.sort;

import algorithm.utils.Utils;
import org.junit.Test;

import java.util.Arrays;

public class QuickSortDemo4 {

    /**
     * 76, 32, 76 是个bug
     */
    @Test
    public void test() {

        for (int i = 0; i < 100; i++) {
            int[] ints = Utils.RandomArr(2);
//            ints = new int[]{76, 32, 76};
            System.out.println(Arrays.toString(ints));
            me(ints, 0, ints.length - 1);
            System.out.println(Utils.checkSort(ints, true));
            System.out.println(Arrays.toString(ints));
        }

    }

    public void me(int[] arr, int low, int high) {
        if (low >= high) {
            return;
        }
        int k = sort(arr, low, high);
        /*
         * 76, 32, 76 是个bug
         * k 本身不用参与
         * 一定要把k剔除掉，不然
         */
//        me(arr, low, k);
        me(arr, low, k - 1);
        me(arr, k + 1, high);
    }

    public int sort(int[] arr, int low, int high) {
        /*
         * 一定要校验
         */
        if (low >= high) return high;
        int i = low;
        int j = high;
        int k = arr[low];
        while (i < j) {
            while (arr[i] <= k && i < j) {
                i++;
            }
            while (k < arr[j] && low < j) {
                j--;
            }
            if (i < j)
                exc(arr, i, j);
        }
        exc(arr, low, j);
        return j;
    }

    public void exc(int[] arr, int a, int b) {
        int i = arr[a];
        arr[a] = arr[b];
        arr[b] = i;
    }

}
